// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include <stack>
#include "commoncppproblem456.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\456.132-模式.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-24 10:25:17
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-24 11:17:36
 */
/*
 * @lc app=leetcode.cn id=456 lang=cpp
 *
 * [456] 132模式
 */

// @lc code=start
// class Solution {
// public:
//     bool find132pattern(vector<int>& nums) {
        
//         if(nums.size() < 2)
//         {
//             return false;
//         }
//         stack<int> stk;
//         stk.push(nums[0]);
//         int n = nums.size();
//         int min = 0;
//         for(int i = 1; i < n ; i++)
//         {
//             if(nums[i] > stk.top() && stk.size() == 1)
//             {
//                 int temp = nums[i];
//                 stk.push(nums[i]);
//             }
//             else if(nums[i] < stk.top() && nums[i] > nums[min] && stk.size() == 2)
//             {
//                 int temp = nums[i];
//                 stk.push(nums[i]);
//                 return true;
//             }
//             else if(nums[i] > stk.top() && stk.size() == 2)
//             {
//                 stk.pop();
//                 stk.push(nums[i]);
//             }else if(stk.size() == 2 && nums[i] < stk.top() && nums[i] < nums[min])
//             {
//                 stk.pop();
//                 stk.pop();
//                 min++;
//                 stk.push(nums[min]);

//             }
//             else if(nums[i] < stk.top() && stk.size() == 1)
//             {
//                 stk.pop();
//                 int temp = nums[i];
//                 min = i;
//                 stk.push(nums[i]);
//             }
//         }
//         return false;
//     }
// };


//  超时
// class Solution {
// public:
//     bool find132pattern(vector<int>& nums) {
        
//         if(nums.size() < 2)
//         {
//             return false;
//         }
//         int n = nums.size();
//         stack<int> stk;
//         int minIndex = 0;
//         while(minIndex < n)
//         {
//             while(!stk.empty())
//             {
//                 stk.pop();
//             }

//             for(int j = minIndex ; j < n; j++)
//             {

//                 if(stk.size() == 0)
//                 {
//                     // 栈无内容，第一个元素入栈
//                     stk.push(nums[minIndex]);
//                 }
//                 else if(stk.size() == 1 && nums[j] > stk.top())
//                 {
//                     // 栈内有一个元素，切遇到比站内元素大的元素，入栈
//                     stk.push(nums[j]);
//                 }
//                 else if(stk.size() == 2 && nums[j] < stk.top() && nums[j] > nums[minIndex])
//                 {
//                     return true;
//                 }
//                 else if(stk.size() == 2 && nums[j] > stk.top() && j != n - 1)
//                 {
//                     stk.pop();
//                     stk.push(nums[j]);
//                 }
//                 else if(n == minIndex - 2)
//                 {
//                     return false;
//                 }
//             }
//             minIndex++;
//         }
//         return false;
//     }
// };


// class Solution {
// public:
//     bool find132pattern(vector<int>& nums) {
//         if(nums.size() < 2)
//             return false;
//         stack<int> stk;
//         int two = INT_MIN;
//         for(int i = nums.size() - 1 ; i >= 0 ; i--)
//         {
//             // 如果找到比二小的元素，
//             if(nums[i] >= two)
//             {
//                 // 如果发现大于栈顶（破坏了单调性），那么要去更新栈和two的数值（two变为更大的数字）
//                 while (!stk.empty() && nums[stk.top()] < nums[i])
//                 {
//                     two = nums[stk.top()];
//                     stk.pop();
//                 }

//                 stk.push(i);
//             }
//             else{
//                 //没找到比二小的元素
//                 return true;
//             }
//         }
//         return false;
  
//     }
// };


class Solution{
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.size() < 2)
        {
            return false;
        }
        stack<int> stk;
        int n = nums.size();
        stk.push(nums[n-1]);
        int 
        for(int i = n - 1;i >= 0;i++)
        {
            if(nums[i] > stk.top() && stk.size() == 1)
            {
                stk.push(nums[i]);
            }
            if(stk.size() == 2 && )

        }
    }
}
//[1,0,1,-4,-3]
//[-2,1,2,-2,1,2]
//[1,4,0,-1,-2,-3,-1,-2]
// @lc code=end

